package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class ConvertBSTToGreaterTree {
	
	//方法一：中序遍历模式的递归版
	public TreeNode convertBST(TreeNode root) {
		dfs(root, new int[] {0});
		return root;
	}
	
    private void dfs(TreeNode node, int[] sum) {
    	if(node == null)
    		return;
    	dfs(node.right, sum);
    	sum[0] = node.val += sum[0];
    	dfs(node.left, sum);
    }
    
    //方法二：中序遍历模式的迭代版
    public TreeNode convertBST2(TreeNode root) {
    	TreeNode p = root;
    	LinkedList<TreeNode> stack = new LinkedList<>();
    	int sum = 0;
    	while(!stack.isEmpty() || p != null) {
    		if(p != null) {
    			stack.push(p);
    			p = p.right; 
    		}else {
    			TreeNode node = stack.pop();
    			sum = node.val += sum;
    			p = node.left;
    		}
    	}
    	
		return root;
    }
}
